package algorithm.foroffer;

import org.junit.Test;

import java.util.*;

/**
 * description:
 *
 * @author liyazhou
 * @create 2017-06-02 20:12
 *
 * 面试题44：扑克牌的顺子
 *
 * 题目：
 *      从扑克牌中随机抽 5 张牌，判断是不是顺子，即这 5 张牌是不是连续的。
 *      2~10为数字本身， A 为 1，J 为 11，Q 为 12，K 为13，而大、小王可以看成任意数字。
 *
 * 考查点：
 *      1. 抽象建模能力
 *
 * 思路：
 *      1. 对非大小王的数字排序
 *             如果有相同的数字，则返回 false
 *             统计大、小王的数目(大小王初始化为0，区分其他的牌)
 *             计算相邻数字之间的差，相差为1，表示连续，相差大于 1，则不连续，统计相邻的牌空缺总数（大于大小王数目，返回 false）
 *
 *
 */
public class Test44 {

    public boolean isContinuous(int[] numbers){
        if (numbers == null || numbers.length != 5) return false;

        // 选择排序
        for (int i = 0; i < numbers.length; i ++){
            for (int j = i; j < numbers.length; j ++){
                // if (numbers[i] == numbers[j]) return false; // 存在相同的数字，不是顺子
                if (numbers[i] > numbers[j]){
                    int tmp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = tmp;
                }
            }
        }

        // 统计大小王的个数
        int counter = 0;
        for (int i = 0; i < 2; i ++){
            if (numbers[i] == 0) counter ++;
        }

        int totalDiff = 0;
        for (int i = 1; i < numbers.length; i ++){
            if (numbers[i-1] == 0) continue; // 前一个数字是0，也即是小大王则跳过
            int diff = numbers[i] - numbers[i-1];
            if (diff == 0) return false;
            totalDiff += (diff - 1);
            if (totalDiff > counter) return false;
        }

        return totalDiff <= counter;
    }

    @Test
    public void test(){
        List<Integer> pokers = new ArrayList<>();
        for (int i = 0; i < 4; i ++){
            for (int j = 1; j < 14; j ++)
                pokers.add(j);
        }
        pokers.add(0);
        pokers.add(0);
        Collections.shuffle(pokers);

        for (int times = 0; times < 10; times ++) {
            int[] selectedPokers = new int[5];
            Random random = new Random();
            for (int i = 0; i < 5; i++)
                 selectedPokers[i] = pokers.get(random.nextInt(pokers.size()));

            boolean isContinuous = isContinuous(selectedPokers);
            System.out.println(Arrays.toString(selectedPokers) + ":\t" + isContinuous);
        }
    }


    /**
     * 2017-8-17 20:16:33
     * @param numbers 数组
     * @return 是否是顺子
     */
    public boolean isContinuous2(int [] numbers) {
        if (numbers == null || numbers.length == 0) return false;

        // Arrays.sort(numbers， Comparator.reverseOrder());
        // Arrays.sort(numbers);

        for (int i = 0; i < numbers.length; i ++){
            int idx = i;
            for (int j = i+1; j < numbers.length; j ++){
                if (numbers[j] < numbers[idx])
                    idx = j;
            }
            if (idx != i){
                int tmp = numbers[i];
                numbers[i] = numbers[idx];
                numbers[idx] = tmp;
            }
        }


        int timesOfZero = 0;
        for (int num : numbers){
            if (num == 0) timesOfZero ++;
            else		  break;
        }

        int diff = 0;
        for (int i = 1; i < numbers.length; i ++){
            if (numbers[i] == numbers[i-1] && numbers[i] != 0) return false;
            if (numbers[i-1] == 0 || numbers[i] == 0) continue;
            diff += numbers[i] - numbers[i-1] - 1;
        }

        boolean isContinuous = false;
        if (timesOfZero >= diff) isContinuous = true;

        return isContinuous;
    }


}
